package com.tgy.algorithm.base._递归;

/**
 * 有一组大于0数字，给定一个值，使用这一组大于0的数计算出这个值，每一个数可以无限次使用
 */
public class _选择数字组合问题 {


    public static int joinSum(int[] nums,int sum) {
        return doJoinSum(nums,0,sum);
    }

    public static int doJoinSum(int[] nums,int curIndex,int rest) {

        if (curIndex >= nums.length) {

            return rest == 0 ? 1:0;
        }

        int ret = 0;
//        for (int i = 0; rest - (nums[curIndex] * i) >= 0; i++) {
        for (int i = 0; (nums[curIndex] * i) <= rest; i++) {
            ret += doJoinSum(nums,curIndex+1,rest - (nums[curIndex]*i));
        }
        return ret;
    }

    public static int joinSum01(int[] nums,int sum) {

        int len = nums.length;
        int[][] cache = new int[len+1][sum+1];

        cache[len][0] = 1;

        for (int i = len - 1; i >= 0; i--) {
            for (int j = 0; j <= sum; j++) {
                int value = cache[i+1][j];
//                for (int k = 0; j - nums[i]*k >= 0; k++) {
//                    value += cache[i+1][j - nums[i]*k];
//                }
                int distance = j - nums[i];
                if (distance >= 0) {
                    // 当前行的cache[i]
                    value += cache[i][distance];
                }
                cache[i][j] = value;
            }
        }

        return cache[0][sum];
    }


    public static int ways4(int[] arr,int aim){
        if(arr == null || arr.length == 0 || aim < 0){
            return 0;
        }
        int N= arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        dp[N][0]=1; // dp[N][1...aim]=0;

        for(int index=N-1;index>=0;index--){
            for(int rest = 0;rest <= aim; rest++) {
                dp[index][rest] = dp[index + 1][rest];
                if (rest - arr[index] >= 0) {
                    dp[index][rest] += dp[index][rest - arr[index]];
                }
            }
        }
        return dp[0][aim];
    }

    public static void main(String[] args) {

        int[] nums = new int[]{5,10,50,100};
        int count = joinSum(nums, 1000);
        int count01 = joinSum01(nums, 1000);
        System.out.println(ways4(nums, 1000));
        System.out.println(count);
        System.out.println(count01);
    }

}
